package edu.whu.rose.clock.kps.algorithm.cbes;

import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import edu.whu.rose.clock.kps.algorithm.SearchAlgorithm;
import edu.whu.rose.clock.kps.algorithm.banks1.SPVertex;
import edu.whu.rose.clock.kps.datastruct.SimpleAnswer;
import edu.whu.rose.clock.kps.datastruct.SimpleMatchedSubgraph;
import edu.whu.rose.clock.kps.datastruct.SimpleSubgraphVertex;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.MyMath;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;
import edu.whu.rose.clock.util.priorityqueue.FibonacciHeapPQ;
import edu.whu.rose.clock.util.priorityqueue.UnderflowException;

public class CESwithPrioritization extends SearchAlgorithm {

	private int groupNum;

	private HashMap<Integer, SimpleMatchedSubgraph> matched_subgraphs;

	private ArrayList<FibonacciHeapPQ<GroupIteratorInSubgraph>> all_iterator_heaps;
	private boolean[] groupEmpty;
	
	private final Date startTime;

	public CESwithPrioritization(
			SimpleMatchedSubgraph[] matched_subgraphs, Date startTime) {
		groupNum = matched_subgraphs[0].groupNum();
		groupEmpty = new boolean[groupNum];
		this.matched_subgraphs = new HashMap<Integer, SimpleMatchedSubgraph>();
		for (int i = 0; i < matched_subgraphs.length; i++) {
			this.matched_subgraphs.put(new Integer(matched_subgraphs[i]
					.getSubgraphID()), matched_subgraphs[i]);
		}
		this.startTime = startTime;
	}

	public void init() {
//		all_matched_vertexes = unionSubgraphVertexes();
		all_iterator_heaps = new ArrayList<FibonacciHeapPQ<GroupIteratorInSubgraph>>();
		for (int i = 0; i < groupNum; i++) {
			all_iterator_heaps.add(new FibonacciHeapPQ<GroupIteratorInSubgraph>());
		}
		Iterator<SimpleMatchedSubgraph> li = matched_subgraphs.values().iterator();
		while (li.hasNext()) {
			SimpleMatchedSubgraph sms = li.next();
			for (int i = 0; i < groupNum; i++) {
				GroupIteratorInSubgraph di = new GroupIteratorInSubgraph(
						sms.getSubgraphMatrix(), sms.getSubgraphID(), i, sms.getGroup(i));
				all_iterator_heaps.get(i).enqueue(di);
			}
		}
	}

	public SimpleAnswer[] process(int k) {
		int size = 0;
		SimpleAnswer[] topk = new SimpleAnswer[k];
//		ArrayList<SimpleAnswer> answers = new ArrayList<SimpleAnswer>();
		
//		HashMap<Integer, HashMap<Integer, boolean[]>> nodeListsInAllSubgraphs = 
//			new HashMap<Integer, HashMap<Integer, boolean[]>>();
		HashMap<Integer, HashMap<Integer, double[]>> distancesInAllSubgraphs = 
			new HashMap<Integer, HashMap<Integer, double[]>>();
		HashMap<Integer, HashMap<Integer, int[]>> predecessorsInAllSubgraphs = 
			new HashMap<Integer, HashMap<Integer, int[]>>();
		
		Iterator<Integer> it = matched_subgraphs.keySet().iterator();
		while (it.hasNext()) {
			Integer I = it.next();
			
//			HashMap<Integer, boolean[]> nodeLists = new HashMap<Integer, boolean[]>();
			HashMap<Integer, double[]> distances = new HashMap<Integer, double[]>();
			HashMap<Integer, int[]> predecessors = new HashMap<Integer, int[]>();
			
//			nodeListsInAllSubgraphs.put(I, nodeLists);
			distancesInAllSubgraphs.put(I, distances);
			predecessorsInAllSubgraphs.put(I, predecessors);
		}
		
		boolean firstk = true;
		boolean overBound = false;
		
		HashSet<SimpleSubgraphVertex> abandoned = new HashSet<SimpleSubgraphVertex>();

		// begin to search
		while (!isEmpty()) {
			try {
				for (int i = 0; i < groupNum; i++) {
					if (all_iterator_heaps.get(i).isEmpty()) {
						groupEmpty[i] = true;
						continue;
					}
					GroupIteratorInSubgraph di = all_iterator_heaps.get(i).dequeueMin();
					int gid = di.getSubgraphID();
					SPVertex spv = di.next();
					int root = spv.getID();
					
					double distance = spv.getDistance();

//					if (gid == 55457 && i == 1) {
//						System.out.println();
//					}
					
					Integer SG = new Integer(gid);
					Integer R = new Integer(root);
					
//					HashMap<Integer, boolean[]> allNodeLists = nodeListsInAllSubgraphs.get(SG);
					HashMap<Integer, double[]> allDistances = distancesInAllSubgraphs.get(SG);
					HashMap<Integer, int[]> allPredecessors = predecessorsInAllSubgraphs.get(SG);
					
					// maintaining predecessor records, which is always necessary
					if (!allPredecessors.containsKey(R)) {
						int[] predecessors = new int[groupNum];
						predecessors[i] = spv.getPredecessor();
						allPredecessors.put(R, predecessors);
					}
					else {
						allPredecessors.get(R)[i] = spv.getPredecessor();
					}
					
					if (abandoned.contains(new SimpleSubgraphVertex(gid, root))) {
						if (di.hasNext()) {
							all_iterator_heaps.get(i).enqueue(di);
						}
						continue;
					}
					
					if (!allDistances.containsKey(R)) {
//						boolean[] nodeLists = new boolean[groupNum];
//						nodeLists[i] = true;
//						allNodeLists.put(R, nodeLists);
						
						// arbitrary new root cannot hold a tree smaller than current topk
						if (overBound) {
							if (di.hasNext()) {
								all_iterator_heaps.get(i).enqueue(di);
							}
							continue;
						}
						
						double[] distances = new double[groupNum];
						distances[i] = distance;
						for (int j = 0; j < groupNum; j++) {
							if (j != i) {
								distances[j] = Double.MAX_VALUE;
							}
						}
						allDistances.put(R, distances);
						
//						int[] predecessors = new int[groupNum];
//						predecessors[i] = spv.getPredecessor();
//						allPredecessors.put(R, predecessors);
					}
					else {
//						allNodeLists.get(R)[i] = true;
						allDistances.get(R)[i] = distance;
//						allPredecessors.get(R)[i] = spv.getPredecessor();
					}
					
					if (crossProduct(i, allDistances.get(R))) {

//						if (root == 115476) {
//							System.out.println();
//						}
						
						SimpleAnswer at = genAnswer(root, allPredecessors);
						size = addTopKAnswer(at, topk, size);
						
						abandoned.add(new SimpleSubgraphVertex(gid, root));
						allDistances.remove(R);
						
						if (size >= k) {
							if (firstk) {
								Date getFirstK = new Date();
								System.out.println(
										"Time exhausted for producing first k answers: " + 
										(getFirstK.getTime() - startTime.getTime()) + "ms");

								double sum = 0.0d;
								for (int n = 0; n < topk.length; n++) {
									SimpleAnswer sa = topk[n];
									System.out.print("Rank " + (n + 1) + ": {" + sa.getScore() + "} ");
									System.out.print(" root[" + sa.getRoot() + "] ");
									sum += sa.getScore();
									for (int y = 0; y < sa.getLeafNumber(); y++) {
										int[] path = sa.getPath(y);
										System.out.print("( ");
										if (path != null) {
											for (int m = 0; m < path.length; m++) {
												System.out.print(path[m] + ", ");
											}
										}
										System.out.print(" )");
									}
									System.out.println();
								}
								System.out.println("Average score: " + (sum / k));
								
								firstk = false;
							}
						}
					}
					
					if (di.hasNext()) {
						all_iterator_heaps.get(i).enqueue(di);
					}
					
					// check if algorithm can be stopped
					if (size < k) {
						continue;
					}
					if (!overBound) {
						double total = 0.0d;
						for (int j = 0; j < groupNum; j++) {
							total += all_iterator_heaps.get(j).findMin().peek();
						}
						if (total >= topk[k - 1].getScore()) {
							overBound = true;
						}
					}
					
					if (overBound) {
						boolean noSmallerTree = true;
						Iterator<Integer> gIt = distancesInAllSubgraphs.keySet().iterator();
						while (gIt.hasNext()) {
							Integer G = gIt.next();
							HashMap<Integer, double[]> diss = distancesInAllSubgraphs.get(G);
							Iterator<Integer> vIt = diss.keySet().iterator();
							while (vIt.hasNext()) {
								Integer V = vIt.next();

								if (V.intValue() == 189489) {
									System.out.println();
								}
								
								double[] dis = diss.get(V);
								double sum = 0.0d;
								for (int j = 0; j < groupNum; j++) {
									if (dis[j] < Double.MAX_VALUE) {
										sum += dis[j];
									}
									else {
										try {
											sum += all_iterator_heaps.get(j).findMin().peek();
										}
										catch (UnderflowException ex) {
											sum = Double.MAX_VALUE;
											break;
										}
									}
								}
								if (sum >= topk[k - 1].getScore()) {
									abandoned.add(new SimpleSubgraphVertex(G.intValue(), V.intValue()));
									vIt.remove();
								}
								else {
									noSmallerTree = false;
								}
							}
						}
						
						if (noSmallerTree) {
							System.out.println("Successfully stopped");
							return topk;
						}
					}
				}
			} catch (UnderflowException ex) {
				ex.printStackTrace();
			}

		}
		System.out.println("All processed");
		return topk;
	}
	
	private boolean isEmpty() {
		for (int i = 0; i < groupNum; i++) {
			if (!groupEmpty[i]) {
				return false;
			}
		}
		return true;
	}
	
	private boolean crossProduct(int i, double[] distances) {
		for (int j = 0; j < groupNum; j++) {
			if (j != i) {
				if (distances[j] == Double.MAX_VALUE) {
					return false;
				}
			}
		}
		return true;
	}
	
	private SimpleAnswer genAnswer(int root, HashMap<Integer, int[]> allPredecessors) {
		int[] leaves = new int[groupNum];
		int[][] paths = new int[groupNum][];
		SequentialIntArray allVertexes = new SequentialIntArray();
		allVertexes.insert(root);
		
		for (int i = 0; i < groupNum; i++) {
			paths[i] = getPath(root, i, allVertexes, 
					allPredecessors);
			if (paths[i] == null) {
				leaves[i] = root;
			}
			else {
				leaves[i] = paths[i][paths[i].length - 1];
			}
			
		}
		
		return new SimpleAnswer(root, leaves, paths, allVertexes.getArray());
	}

	private int[] getPath(int root, int i,
			SequentialIntArray allVertexes, HashMap<Integer, int[]> allPredecessors) {
		ExpandableIntArray eia = new ExpandableIntArray();
		int current = root;
		
		do {
			current = allPredecessors.get(new Integer(current))[i];
			if (current == 0) {
				System.err.println("Error: predecessor not found");
				System.exit(1);
			}
			else if (current != -1) {
				allVertexes.insert(current);
				eia.add(current);
			}
			else {
				break;
			}
		} while (true);
		
		return eia.toArray();
	}
	
	private int addTopKAnswer(SimpleAnswer answer, SimpleAnswer[] topk, int size) {
		int pos = -1;
		boolean inserted = false;
		for (int i = 0; i < size; i++) {
			int x = answer.compare(topk[i]);
			if (x == MyMath.ARR1_CONTAIN_ARR2) {
				return size;
			}
			else if (x == MyMath.ARR2_CONTAIN_ARR1) {
				if (!inserted) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					inserted = true;
				}
				else {
					for (int j = i; j < size - 1; j++) {
						topk[j] = topk[j + 1];
					}
					size--;
				}
			}
			else if (x == MyMath.ARR1_EQUAL_ARR2) {
				if (answer.getScore() < topk[i].getScore()) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					return size;
				}
				else {
					return size;
				}
			}
			
			if (answer.getScore() >= topk[i].getScore()) {
				pos = i;
			}
		}
		
		if (inserted) {
			return size;
		}
		
		if (pos < size - 1) {
			if (size < topk.length) {
				for (int i = size; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
				size++;
			}
			else {
				for (int i = topk.length - 1; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
			}
			topk[pos + 1] = answer;
		}
		else if (size < topk.length) {
			topk[size] = answer;
			size++;
		}
		
		return size;
	}

	private void addTopKAnswer(SimpleAnswer answer, ArrayList<SimpleAnswer> answers, int k) {
		if (answers.size() == 0) {
			answers.add(answer);
			return;
		}
		
		int pos = 0;
		for (int i = 0; i < Math.min(k, answers.size()); i++) {
			int x = answer.compare(answers.get(i));
			if (x == MyMath.ARR1_CONTAIN_ARR2) {
				return;
			}
			else if (x == MyMath.ARR2_CONTAIN_ARR1) {
				answers.remove(i);
			}
			else if (x == MyMath.ARR1_EQUAL_ARR2) {
				if (answer.getScore() < answers.get(i).getScore()) {
					answers.remove(i);
				}
				else {
					return;
				}
			}
			
			if (i < answers.size() && answer.getScore() >= answers.get(i).getScore()) {
				pos = i;
			}
		}
		
		if (pos < k - 1) {
			if (pos == answers.size() - 1) {
				answers.add(answer);
			}
			else {
				answers.add(answers.get(answers.size() - 1));
				for (int i = Math.min(k - 1, answers.size()); i > pos + 1; i--) {
					answers.set(i, answers.get(i - 1));
				}
				answers.set(pos + 1, answer);
			}
		}
		
//		if (answers.size() == 0) {
//			answers.add(answer);
//			return;
//		}
//		
//		int low = 0;
//		int mid = 0;
//		int top = answers.size() - 1;
//		while (low <= top) {
//			mid = (low + top) / 2;
//			if (answer.compare(answers.get(mid)) > 0) {
//				low = mid + 1;
//			}
//			else if (answer.compare(answers.get(mid)) < 0) {
//				top = mid - 1;
//			}
//			else {
//				answers.add(answers.get(answers.size() - 1));
//				for (int i = answers.size() - 2; i > mid; i--) {
//					answers.set(i, answers.get(i - 1));
//				}
//				answers.set(mid, answer);
//				return;
//			}
//		}
//		answers.add(answers.get(answers.size() - 1));
//		for (int i = answers.size() - 2; i > low; i--) {
//			answers.set(i, answers.get(i - 1));
//		}
//		answers.set(low, answer);
	}

//	private HashSet<SimpleSubgraphVertex> unionSubgraphVertexes() {
//		HashSet<SimpleSubgraphVertex> result = new HashSet<SimpleSubgraphVertex>();
//		matched_vertexes_in_subgraph = new HashMap<Integer, HashSet<Integer>>();
//		Iterator<Integer> it = matched_subgraphs.keySet().iterator();
//		while (it.hasNext()) {
//			Integer I = it.next();
//			HashSet<Integer> set = new HashSet<Integer>();
//			SimpleMatchedSubgraph sms = matched_subgraphs.get(I);
//			for (int j = 0; j < sms.groupNum(); j++) {
//				for (int k = 0; k < sms.groupSize(j); k++) {
//					SimpleSubgraphVertex sv = new SimpleSubgraphVertex(
//							sms.getSubgraphID(),
//							sms.getVertex(j, k));
//					result.add(sv);
//					set.add(new Integer(sms.getVertex(j, k)));
//				}
//			}
//			matched_vertexes_in_subgraph.put(new Integer(sms
//					.getSubgraphID()), set);
//		}
//		return result;
//	}

}
